{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Tutorial: Informed Search Algorithms and CommonRoad Search\n",
    "\n",
    "This tutorial shows how we can use motion primitives in informed search algorithms to find a trajectory that connects an **initial state** and a **goal region**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## How to use this tutorial\n",
    "Before you start with this tutorial, make sure that \n",
    "* you have read through the tutorial for [CommonRoad-io](https://commonroad.in.tum.de/static/docs/commonroad-io/index.html). Its tutorial can be found [here](https://commonroad.in.tum.de/tutorials/).\n",
    "* you have installed all necessary modules for CommonRoad Search according to the installation manual.\n",
    "* you have done the tutorial on uninformed search algorithms and CommonRoad Search. \n",
    "\n",
    "\n",
    "Let's start with importing the modules and loading the commonroad scenario. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import sys\n",
    "sys.path.append(\"../../GSMP/motion_automata\")\n",
    "from commonroad.common.file_reader import CommonRoadFileReader\n",
    "from commonroad.visualization.draw_dispatch_cr import draw_object\n",
    "from automata.HelperFunctions import load_scenario, generate_automata\n",
    "from automata.helper_tree_search import *\n",
    "import automata.tree_search as tree_search"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAA2AAAAA+CAYAAABN/ni+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAKXElEQVR4nO3dbYxc51XA8f/Zndl1ujGyq4a0OIYGlCIVW20jN4lFW5WXhLRCdeEDSspLeZFMpSaiIgha+EDVT6WklSAgwKiRitQkbQQGC0HboCL6JQuOTYTtNCHrrSN7a5I6adiuyzqzO4cPc23Wzow9ITP33t37/0nWzDx7587RHJ87c2ae+0xkJpIkSZKk8ZuoOgBJkiRJagobMEmSJEkqiQ2YJEmSJJXEBkySJEmSSmIDJkmSJEklsQGTJEmSpJK0htkoIk4A3wFWgZXM3DXOoCRJkiRpIxqqASv8WGaeGVskkiRJkrTBOQVRkiRJkkoSmXnljSK+AXwbSOAvMnPf5bZ/+OGH8+TJk6OJUJIkSZLWmXvuuedMZl5z6fiwUxDfkZkLEfG9wCMR8WRmfm3tBhGxF9gL8Oijj7J9+/ZXHbQkSZIkrVPP9BscagpiZi4Ul88B+4Gb+myzLzN3uUCHJEmSJPV3xQYsImYiYvP568BtwNEr3Gc00UmSJEnSBjLMFMRrgf1FU9UCHsjML13uDlu3bqXT6bC0tMQw55hJkiRJUhNcsQHLzHngLa9op60WrVaLdrttIyZJkiRJhVfyO2CvfOdFIzY1NcXy8jJnz54d58NJkiRJUq2NtQED6Ha7ZCYRwczMzLgfTpIkSZJqa2wN2Orq6oXph91ud1wPI0mSJEnrxlgasOXlZRsvSZIkSbrEWBqwxcXFcexWkiRJkta1oX6IWZIkSZL06tmASZIkSVJJbMAkSZIkqSRjOQfs0KFDzM3NjWPXkiRJkrRuRWaOfKezs7Oj36kkSZIkrRO7d+8+lJm7Lh13CqIkSZIklWSoBiwibo+IpyJiLiI+OsT2rz4ySdqAuisrLD//PIvz85w5+BgvHnui6pAkSVKJrngOWERMAn8K3AqcAg5GxIHMHPiuYevWrXQ6HZaWlhjHFEdJWk+evvczTK+sEp0OE6srbCK4CtgcwYlN02z5kTdXHWJtfPVv74VzC6Pb4fQ2fvz9vzW6/UmS9CoNswjHTcBcZs4DRMRDwB5gYAPWarVotVq0220bMUkjc+TIixw+/AI33vhadu7cUnU4Q9t07iXectVVMDX1sr+dfOlcBRHV2LkF7rp1dIs4/ckjI9uVJEkjMUwDtg04ueb2KeDmoXZeNGJTU1MsLy9z9uzZ/0+MksSRIy9y990H6XS6tNsT3Hff29dNE5bt9sC/RadTYiSSJKlqI1uGPiL2AnsBjh8/fmG82+2SmUQEMzMzo3o4SQ1z9OgpOp0u3S6srHQ5enSJW27ZVnVYQ5nYtAlWVvr+rd1NNrXbTPb5dqyJJidHuzbU5OSErz2SpFoZpgFbALavuX1dMXaRzNwH7AOYn5/P1dXVC9MPu93uSIKV1Fw7dlxNuz1Bp9Ol1Zpgx46r18236iuTE9C//2Ka5Nvf/CZXXXNNuUHV1OrqaF8vVle76+b/iSSpGYZpwA4CN0TE9fQarzuAD1zuDsvLyzZekkZq584t3Hff29flOWA5Pc1T3zrDuUxyqk222r3Ldpt8/eu57jWvqTpESZJUkis2YJm5EhF3AV8GJoH7M/PY5e6zuLg4ovAk6f/s3LllXTVe523/hQ/QPXeO9ubNxIQ/v3hZ09tGu3DG9PqYpipJao4Yx+qEs7OzLnkoSZIkqbF27959KDN3XTruR7GSJEmSVBIbMEmSJEkqyVimIEbEt4BnRr7j0XkdcKbqIHSB+agX81Ev5qNezEe9mI96MR/1Yj6q9wOZ+bJljsfSgNVdRDzWbz6mqmE+6sV81Iv5qBfzUS/mo17MR72Yj/pyCqIkSZIklcQGTJIkSZJK0tQGbF/VAegi5qNezEe9mI96MR/1Yj7qxXzUi/moqUaeAyZJkiRJVWjqN2CSJEmSVLpGNWARcXtEPBURcxHx0arjaZqI2B4R/xwRT0TEsYj4jWL84xGxEBGPF//eW3WsTRERJyLiSPG8P1aMvTYiHomIp4vLrVXH2QQR8cNrauDxiFiMiI9YH+WKiPsj4rmIOLpmrG9NRM8fF68p/xERN1YX+cY0IB9/GBFPFs/5/ojYUoy/MSL+Z02t/Hl1kW9MA/Ix8BgVER8r6uOpiPipaqLeuAbk4wtrcnEiIh4vxq2PGmnMFMSImAT+E7gVOAUcBO7MzCcqDaxBIuINwBsy83BEbAYOAe8Hfg5Yysx7Kw2wgSLiBLArM8+sGfsU8EJmfrL4oGJrZv5OVTE2UXG8WgBuBn4F66M0EfEuYAn4q8zcUYz1rYnijebdwHvp5eqPMvPmqmLfiAbk4zbgq5m5EhF/AFDk443A35/fTqM3IB8fp88xKiLeDDwI3AR8H/BPwJsyc7XUoDewfvm45O+fBv47Mz9hfdRLk74BuwmYy8z5zHwJeAjYU3FMjZKZpzPzcHH9O8DXgW3VRqU+9gCfK65/jl6TrHL9BHA8M+v8g/YbUmZ+DXjhkuFBNbGH3hufzMxZYEvxQZNGpF8+MvMrmblS3JwFris9sIYaUB+D7AEeysxzmfkNYI7eezGNyOXyERFB7wPuB0sNSkNpUgO2DTi55vYpfPNfmeKTmLcB/1oM3VVMJ7nfKW+lSuArEXEoIvYWY9dm5uni+n8B11YTWqPdwcUvmtZHtQbVhK8r1ftV4B/X3L4+Iv49Iv4lIt5ZVVAN1O8YZX1U653As5n59Jox66MmmtSAqSYi4mrgr4GPZOYi8GfADwFvBU4Dn64wvKZ5R2beCLwH+HAxneGC7M1RbsY85ZqIiCngfcDDxZD1USPWRH1ExO8BK8Dni6HTwPdn5tuA3wQeiIjvqSq+BvEYVU93cvEHedZHjTSpAVsAtq+5fV0xphJFRJte8/X5zPwbgMx8NjNXM7ML/CVOUShNZi4Ul88B++k998+en0ZVXD5XXYSN9B7gcGY+C9ZHTQyqCV9XKhIRvwz8NPDzRVNMMdXt+eL6IeA48KbKgmyIyxyjrI+KREQL+FngC+fHrI96aVIDdhC4ISKuLz5hvgM4UHFMjVLMR/4s8PXM/Mya8bXnTPwMcPTS+2r0ImKmWAyFiJgBbqP33B8APlhs9kHg76qJsLEu+tTS+qiFQTVxAPilYjXEW+id7H663w40OhFxO/DbwPsy87trxq8pFrAhIn4QuAGYrybK5rjMMeoAcEdETEfE9fTy8W9lx9dQPwk8mZmnzg9YH/XSqjqAshSrJd0FfBmYBO7PzGMVh9U0Pwr8InDk/LKowO8Cd0bEW+lN6zkB/Ho14TXOtcD+Xl9MC3ggM78UEQeBL0bErwHP0DuJVyUoGuFbubgGPmV9lCciHgTeDbwuIk4Bvw98kv418Q/0VkCcA75Lb8VKjdCAfHwMmAYeKY5fs5n5IeBdwCciogN0gQ9l5rALRmgIA/Lx7n7HqMw8FhFfBJ6gN1X0w66AOFr98pGZn+Xl5xGD9VErjVmGXpIkSZKq1qQpiJIkSZJUKRswSZIkSSqJDZgkSZIklcQGTJIkSZJKYgMmSZIkSSWxAZMkSZKkktiASZIkSVJJbMAkSZIkqST/C8cizaIeFMYDAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 1080x360 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Load scenario ZAM_Urban-3_2\n",
    "scenario_path = '../../scenarios/tutorial/'\n",
    "scenario_id = 'ZAM_Tutorial_Urban-3_2'\n",
    "\n",
    "scenario, planning_problem_set = CommonRoadFileReader(scenario_path+scenario_id+'.xml').open()\n",
    "\n",
    "# Plot scenario and planning problem set\n",
    "\n",
    "plt.figure(figsize=(15, 5))\n",
    "draw_object(scenario)\n",
    "draw_object(planning_problem_set)\n",
    "plt.gca().set_aspect('equal')\n",
    "plt.margins(0, 0)\n",
    "plt.show()\n",
    "\n",
    "planning_problem = list(planning_problem_set.planning_problem_dict.values())[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Generating a Maneuver Automaton\n",
    "\n",
    "In the following, we load the motion primitives from an XML-File and generate a Maneuver Automaton.\n",
    "The maneuver automaton for this tutorial consists of 7 motion primitives and stores the connectivity to other motion primitives. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Reading motion primitives...\n",
      "Automata created.\n",
      "Number of loaded primitives: 7\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAewAAAHSCAYAAAAuWvi9AAAABHNCSVQICAgIfAhkiAAAAAlwSFlzAAALEgAACxIB0t1+/AAAADh0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uMy4yLjEsIGh0dHA6Ly9tYXRwbG90bGliLm9yZy+j8jraAAAgAElEQVR4nOzdd3iURdsF8DMJvQpSVDCASpVupPcmIlIUKYIUaYq9F7CgItiwvShNBDVELCgoIE2aBaSKEHrvvQcISeb747DfJiGBhOzus+X8ritXks2yO0jcszPP3PcYay1ERETEv4U5PQARERG5MgW2iIhIAFBgi4iIBAAFtoiISABQYIuIiAQABbaIiEgAyOL0ANJSqFAhW7JkSaeHISIi4jPLly8/bK0tnNrP/DawS5YsiWXLljk9DBEREZ8xxuxI62daEhcREQkACmwREZEAoMAWEREJAApsERGRAKDAFhERCQAKbBERkQCgwBYREQkACmwREZEAoMAWEREJAApsERGRAKDAFhERCQAKbBERkQCgwBYREQkACmwREZEAoMAWEREJAApsERGRlKKigJIlgbAwfo6KcnpEyOL0AERERPxKVBTQrx8QG8vvd+zg9wDQtatjw9IMW0REJKmBA91h7RIby9sdpMAWERFJaseO1G/fudO340hBgS0iIuKSkADkyZP6zyIifDuWFBTYIiIiAHDhAvDAA8Dp00CWFFu8cuUChgxxZlwXKbBFRETOnwc6dgSio4GhQ4Hx44ESJQBj+Hn0aEc3nAHaJS4iIqEuNha4917gt9+Ajz8GHn+ctzsc0CkpsEVEJHSdOgW0aQMsWACMGQP06eP0iNKkwBYRkdB0/Dhw553A0qXAN98A99/v9IguS4EtIiKh5/BhoEULYM0a4PvvgfbtnR7RFSmwRUQktOzbBzRrBmzdCkyZwll2AFBgi4hI6Ni5E2jalKE9fTrQuLHTI0o3BbaIiISGzZsZ1idOALNnA7VrOz2iDFFgi4hI8IuJ4TJ4XBzw++9A9epOjyjD1DhFRESC26pVQMOGgLXA/PkBGdaAAltERILZkiW8Tp0zJ7BwIVCxotMjumoKbBERCU4LFnAZvGBBYNEioHRpp0eUKQpsEREJPjNnslyreHHOrEuUcHpEmabAFhGR4DJlCtuNlinDWXaxYk6PyCMU2CIiEjy+/ZYHeVStCsybBxQp4vSIPEaBLSIiweHLL9kPvE4d1lkXKOD0iDxKgS0iIoFvxAjgwQeB5s15TGa+fE6PyOMU2CIiEtjefRd49FFet546FciVy+kReYUCW0REApO1wOuvAy+8AHTqBPzwA5A9u9Oj8hq1JhURkcBjLfD888D77wM9ewJjxwLh4U6Pyqs0wxYRkcCSmMgl8PffBwYMAL74IujDGlBgi4hIIElIAHr3Bj77DHjuOeB//wPCQiPKQuNvKSIige/CBaBrV2D8eF67fucdwBinR+UzHglsY0xLY8wGY8xmY8yLadynozEmxhiz1hgz0RPPKyIiIeLcOTZEmTSJu8Jfey2kwhrwwKYzY0w4gBEAmgPYDWCpMWaqtTYmyX1KA3gJQF1r7TFjTPC0nhEREe+KjQXatWMzlBEjeN06BHlihl0DwGZr7VZrbRyAbwG0TXGfvgBGWGuPAYC19qAHnldERILdyZNAy5bA3LnAuHEhG9aAZwK7GIBdSb7fffG2pMoAKGOM+dMYs9gY09IDzysiIsHs6FF2LvvrLyAqCujVy+kROcpXddhZAJQG0AhAcQALjTGVrLXHk97JGNMPQD8AiIiI8NHQRETE7xw8CLRoAaxbB/z4I9A25cJt6PHEDHsPgBuTfF/84m1J7QYw1Vp7wVq7DcBGMMCTsdaOttZGWmsjCxcu7IGhiYhIwNmzB2jYENi4EfjlF4X1RZ4I7KUAShtjShljsgHoDGBqivv8DM6uYYwpBC6Rb/XAc4uISDDZvh1o0ADYvZuHeLRo4fSI/EamA9taGw/gUQAzAawD8J21dq0x5g1jTJuLd5sJ4IgxJgbAPADPWWuPZPa5RUQkiGzcyLA+ehSYM4dfy/8z1lqnx5CqyMhIu2zZMqeHISIivrBmDdCsGTuZzZ4NVK3q9IgcYYxZbq2NTO1n6nQmIiLOWrECaNSILUYXLgzZsL4SBbaIiDjn77+BJk2A3LkZ1uXLOz0iv6XAFhERZ8ybxzrrwoWBRYuAW25xekR+TYEtIiK+N2MG0KoVUKIEZ9bqvXFFCmwREfGtyZNZW12+PLBgAXD99U6PKCAosEVExHeiooCOHYHISOD334FChZweUcBQYIuIiG+MGQM88ABQvz4waxZwzTVOjyigKLBFRMT7Pv4Y6NcPuOMOYPp0IE8ep0cUcBTYIiLiXUOHAk8+CbRvD/z8M5Azp9MjCkgKbBER8Q5rgUGDgJdfBu6/H/juOyB7dqdHFbB8dbymiIiEEmuBp58GPvoI6NMHGDkSCA93elQBTTNsERHxrMRE4OGHGdaPPQaMGqWw9gAFtoiIeE58PNCzJ0P6xRe52SxMUeMJWhIXERHPiIvjteoffwTeegsYONDpEQUVve0REZHMO3cOuOcehvXw4cEX1lFRQMmSXC0oWZLf+5hm2CIikjlnzrDV6O+/c3NZ//5Oj8izoqJYQx4by+937OD3ANC1q8+GoRm2iIhcvRMn2Axl3jxgwoTgC2uAqwWusHaJjfX5KoJm2CIicnWOHGFY//sv8O23wH33OT0i79ixI/Xbd+706TAU2CIiknEHDgDNmgGbNgE//QS0bu30iDzvxAngjTfS/rmPjwTVkriIiGTM7t1AgwbA1q3Ar78GX1gnJgJffAGUKQN8+CHQuPGl7VRz5QKGDPHpsBTYIiKSflu38rStffuAmTM5yw4mf/0F1KjB7mylSwPLlnEz3ZgxQIkSgDH8PHq0TzecAVoSFxGR9Fq/ngEdGwvMnQvcfrvTI/KcPXuAF17gjvBixYCJE4HOnRnQAMPZxwGdkgJbRESubPVqoHlzfj1/PlC5sqPD8Zhz51g3/vbb7NI2aBA7tOXO7fTILqHAFhGRy1u6lLvBc+XizLpsWadHlHnWAlOmAM88w2X+9u2BDz4ASpVyemRp0jVsERFJ2x9/AE2bAvnzA4sWBUdYx8TwDUj79txMNmcOMHmyX4c1oMAWEZG0zJnDYLv+eoa1nwfaFR0/Djz5JJfzly4FPvkEWLWKb0gCgJbERUTkUtOmAffey53Sc+YARYs6PaKrl5DAMq2BA4GjR9lW9M03gUKFnB5ZhmiGLSIiyX3/PdCuHVCpEjeYBXJY//EHd7P37w9UqAAsXw58/nnAhTWgwBYRkaS++orlTDVrcmZ97bVOj+jq7NoFdOnCmvHDh9k6df58oGpVp0d21RTYIiJCo0YBPXqws9fMmdxoFmjOnuVZ3OXKAT//DLz6KuvHO3Vy11QHKF3DFhERtuB8+mngrruAH34AcuRwekQZYy17mj/zDLB9O9ChA/Deezy7Okhohi0iEsqs5Yz06acZcpMnB15Yr1nDDmz33gvkzctWot9/H1RhDSiwRURCl7XAyy8Dr7wCPPAAEB0NZMvm9KjS7+hR4LHHeF161SpgxAhgxQou6QchLYmLiISixETgqadYi9y/P/DZZ0BYgMzhEhJ4+MYrrwDHjgEPPcRjMAN1g1w6Bci/joiIeExCAkP6k08Y2p9/HjhhvWABUL06MGAAy85WruTMOsjDGlBgi4iElgsXgO7dgbFjedDFBx8Exu7pnTu507tRI3Ys+/57XqsOlkNI0kFL4iIioeL8edYm//QTT6d66SWnR3RlsbHc7f3OO/x+8GDguefYAzzEKLBFRELB2bPAPfcAv/0GfPwx8PjjTo/o8qxledmzz7pn1+++C0REOD0yx2hJXEQk2O3ZA7RowWYoY8b4f1ivXg00aQJ07AgUKMAOZd9+G9JhDSiwRUSC25QpQJUqLHeaOBHo08fpEaXtyBFuJqtWDfjvP26GW74caNjQ6ZH5BQW2iEgwOnsWeOQRHuJx440M7M6dnR5V6uLjudO7dGmWaz3yCLBxI8u1wsOdHp3f0DVsEZFgs2YNN5etWcOyraFDgezZnR5V6ubN4xL9mjVcBv/4Y6BiRadH5Zc0wxYRCRbWsgHK7bcDBw8CM2YAw4f7Z1i7+n03aQKcPs2WqHPmKKwvQzNsEZFgcOQI0Ls3r1nfcQcwYYJ/nmMdGwsMG8ZSrbAw4M03eWBHCJZpZZQCW0Qk0M2bB3TrBhw6xEYoTz7pf53LrAUmTWIN9e7dXLJ/912geHGnRxYw/OxfVERE0u3CBWDgQKBpUyBPHmDxYp665W9hvWoVd3p36QIULgwsWsQd6wrrDPGzf1UREUmXrVuB+vXZsaxXL5Y/Va/u9KiSO3yYO71vuw1Yt447wJcuBerVc3pkAckjgW2MaWmM2WCM2WyMefEy97vXGGONMZGeeF4RkZA0cSKPlFy/nsvMX3zBGba/uHCBB4uULs2e5Y89xjKtvn1VppUJmQ5sY0w4gBEA7gRQAUAXY0yFVO6XF8ATAJZk9jlFRELSqVNAjx5A1648qWrVKnYD8ydz5vDNxBNPcLf66tXARx+xY5lkiidm2DUAbLbWbrXWxgH4FkDbVO73JoB3AJzzwHOKiISWZcu45P3NN8Crr/KYyZIlnR6V29atQPv2QPPmwLlzwM8/sxVqhUvmb3KVPBHYxQDsSvL97ou3/T9jTHUAN1prp3ng+UREQkdiIkugatdmEM6bxxOrsvhJkc/p0zyms0IFYPZsXlNfuxZo2zYwju0MIF7/FzfGhAEYDqBnOu7bD0A/AIgI8SbvIiLYt49L4LNn86StMWOAggWdHhVZy2vpL7zAw0W6dWN9dbFiV/6zclU8McPeA+DGJN8Xv3ibS14AFQHMN8ZsB1ALwNTUNp5Za0dbayOttZGFCxf2wNBERALUtGlA5crAH38Ao0bxqEl/CesVK7hDvVs34LrrgD//BL7+WmHtZZ4I7KUAShtjShljsgHoDGCq64fW2hPW2kLW2pLW2pIAFgNoY61d5oHnFhEJLufOccNW69bADTfw2nW/fv6xvHzwIHd6R0Zy1/fYscA//wB16jg9spCQ6cC21sYDeBTATADrAHxnrV1rjHnDGNMms48vIhIy1q0DatViSdTjjwNLlvjHpq0LF4APPwTKlAHGj+eBIps2sRWqvzVpCWIeuYZtrZ0OYHqK215N476NPPGcIiJBw1pen37ySSB3buCXXzjD9gczZ3Jc69ezR/lHHwHlyjk9qpCkt0YiIk46epSnVvXvD9Sty7plfwjrzZuBNm2Ali05w546lad/Kawdo8AWEXHKwoVAlSoMw3fe4Wz2+uudHdOpU8BLLwG33soSsmHDWKZ1993+cR09hPlJIZ+ISAiJjwfeeAMYMgS46Sbgr7/YFcxJiYlAVBTLtPbtA7p3B4YO5cY38QsKbBERX9q+na1F//qLNdaffgrkzevsmJYu5Sa3xYv5xmHyZG5+E7+iJXEREV/57jv22f7vP85mx493NqwPHAAefBCoUQPYtg0YN46hrbD2SwpsERFvO3OGJVCdOnHT1qpVwP33OzeeuDjg/fd5mtY33wDPPsu66l69VKblx7QkLiLiTStWAF26sG755ZeB118HsmZ1bjwzZrBMa+NGoFUrd321+D29lRIR8YbERGD4cC4vnz4NzJ3LTWZOhfXixTxJq1Ur1n1Pm8YPhXXAUGCLiHjagQPAXXcBzzzDgFy9Gmjc2JmxrFzJkqzatYF//+WbiDVrOC4JKApsERFPmjmTh3bMnw+MGAH89BNw7bW+H0dMDHDffTxD+48/eOzl1q1sK5otm+/HI5mmwBYR8YTz5zmjbtkSKFyYpVIDBvi+2cjmzcADDwAVKwK//Qa88gp3gL/0EpAnj2/HIh6lTWciIpm1YQM3lq1cyZB+/30gZ07fjmHnTuDNN4Evv+QM+tlngeefBwoV8u04xGsU2CIiV8taBuRjjwE5cgA//wy0bevbMezbx+Xu0aP5/YABnE073eJUPE6BLSJyNY4f54Ed333HDWVffw0UK+a75z98mP3H//c/tjrt1QsYNAiIiPDdGMSnFNgiIhn1559sL7p7N2e3zz8PhIf75rmPHwc++IDHXJ45A3TrBrz2GnDzzb55fnGMAltEJL0SElhLPXgwUKIEg7tmTd8896lTwCef8Pr48ePcAf7660CFCr55fnGcAltEJD127uRsdtEizq4/+wzIl8/7z3v2LJ9r2DAug999N0/6qlrV+88tfkVlXSIiV/Ljjzy3euVK4Kuv2H/b22F9/jyD+uabueO7WjV2K5s6VWEdohTYIiJpiY0F+vUDOnTgQRkrV7LG2Zvi43lqVtmywCOPALfcwiYss2b5bvld/JICW0QkNf/+C0RGAmPGcFPZH38wPL0lIQGYOBEoX54nexUpwq5pCxYADRt673klYCiwRUSSspabu2rUAI4dA2bPZvmUt9p5WgtMnswl965dgVy5gClTgCVLgBYtfN8pTfyWAltExOXQIW7qeuIJnmy1ejXQrJl3nstaYPp0zuLvvZdL4ZMmcdm9TRsFtVxCgS0iAnAmXbkyMGcOZ9i//MKe4N7w++9A3bo80evYMWDCBJ6g1bEjEKaXZUmdfjNEJLTFxfEadYsWQIECwD//sNWoN2a4f/4JNGkCNG0K7NoFjBrFPuTduwNZVGUrl6fAFpHQtXkzZ7rvvcfd4MuWcZbtacuX8/zpevV47OXHHwObNvE5s2b1/PNJUNJbOhEJPday9/cjjzAwf/wRuOcezz/PmjXAq6/yTOyCBbl57ZFHgNy5Pf9cEvQ0wxaR0HLyJDuW9egBVK/O8i1Ph/XGjcD993O2PncuW5lu28ald4W1XCXNsEUkdCxezCDduZPtPV9+2bOHdmzfzsedMIHHbb74IruUFSzoueeQkKXAFpHgl5DA5ehXXwWKFwcWLgTq1PHc4+/Zw0NBxo7lLu8nngBeeAEoWtRzzyEhT4EtIsFtzx4ugc+fD3TqBIwcCVxzjWce++BBHsrx2Wd8U9C3LzBwoG/PxZaQocAWkeA1ZQrw4IM8SGPcOKBnT8+Uax09ymMuP/mEp2n16AG88gpQqlTmH1skDQpsEQk+Z88CzzwDfP45N5ZFRwNlymT+cU+eZEnW++/zfOrOnYHXXuNBHSJepsAWkeCyZg2DdO1ahvaQIUD27Jl7zNhYYMQIXgc/cgRo146byypV8syYRdJBZV0iEhysZahGRgKHDwO//caZcGbC+vx54NNPgZtuYklWjRrA0qWsq1ZYi49phi0ige/wYR5JOXUq0LIlMH585nZoX7gAfPkl8NZbbCHaqBGbq9St66kRi2SYZtgiEtjmzePRlDNmAMOHA9OmXX1YJySwA1q5ckD//tztPWeO+7AOEQcpsEUkMF24wMYnTZsCefPy/Oinnrq6064SE4HvvwcqVuRBHPnzM/j/+ouPr6MuxQ8osEUk8GzdCtSvDwwdyrKt5cuBatUy/jjW8hjN6tXdR1v+8AMPAWnVSkEtfkWBLSKBJSoKqFoVWL8emDSJ3cUy2p/bWp5/XasW0KYNcOYM8M03wOrVwL336kxq8Uv6rRSRwLB5M9ClC7uWVarEQzs6dsz44yxaxE1kLVoA+/cz8GNigK5dPdtXXMTDFNgi4t82bWInsXLlgJ9/Bl5/HViwAChRImOP888/wB13AA0a8DH/9z+eqtW7t86kloCgsi4R8U8bNrCsauJE1lI//jjw3HPA9ddn7HH+/ZeHfkydChQqxNrshx8GcuXyzrhFvESBLSL+Zd06BvW33zKon3qKQZ3RUq116zgb/+477vp+6y2Gft68Xhm2iLcpsEXEP8TEAG++yY1kOXOyreizzwJFimTscbZuBQYP5iayXLmAQYOAp58GChTwzrhFfESBLSLOWrOGQf399wzY559nWBcunLHH2bWLs+hx44AsWRjSzz+f8ccR8VMKbBFxxn//8QCNH34A8uQBXnqJy9+FCmXscfbvZz32yJEs13roITZUyei1bhE/p8AWEd/6918G9eTJvJ48aBCDumDBjD3OkSPAu+/ycI64OKBXLz5WRnePiwQIj5R1GWNaGmM2GGM2G2NeTOXnTxtjYowxq40xc40x+j9KJNSsXAm0b8+mJ3PmcOf2jh1cDs9IWJ84wTOoS5UC3nuPjU7WrwfGjFFYS1DL9AzbGBMOYASA5gB2A1hqjJlqrY1JcreVACKttbHGmIcBvAugU2afW0QCwPLl3AT2yy/crf3aa8ATT2R8E9j27Qzlzz8Hjh0DOnTgLvBbb/XGqEX8jieWxGsA2Gyt3QoAxphvAbQF8P+Bba2dl+T+iwF088Dziog/W7qUQT1tGsP5jTdYVpU/f/ofIz4emD4dGDWKp3EZw1air756db3DRQKYJwK7GIBdSb7fDaDmZe7fG8AMDzyviPijJUsY1DNmcKn7rbeAxx4D8uVL/2Ps2QN88QVn1Lt3AzfcALzyCtCnD3Djjd4bu4gf82lrUmNMNwCRAN5L4+f9jDHLjDHLDh065MuhiUhm/f030LIlD9T45x/g7be5jD1wYPrCOjERmDmT17lLlODS+a23Aj/9xGvdgwcrrMU/REUBJUvykJiSJfm9D3hihr0HQNL/i4pfvC0ZY0wzAAMBNLTWnk/tgay1owGMBoDIyEjrgbGJiLf9+SfDdPZslmQNGwYMGJD+jmIHDgBffgmMHg1s28a66eeeA/r2BW66ybtjF8moqCigXz8gNpbf79jB7wEeIONFxtrM5aIxJguAjQCagkG9FMD91tq1Se5TDcAPAFpaazel53EjIyPtsmXLMjU2EfGiRYsY1HPnukP24YdZU30l1gLz5/Pa9OTJwIULQOPGQP/+nGFny+b14YtkmLW8PLN//6U/K1GCK0qZZIxZbq2NTO1nmZ5hW2vjjTGPApgJIBzAOGvtWmPMGwCWWWungkvgeQB8b3gg/E5rbZvMPreIOGDBAgb1vHlsG/r++2xWkp4zqY8eBSZMYFBv2MDNaI8+yhlKuXLeH7vI1VizBoiO5kdqYQ0AO3d6fRgeaZxirZ0OYHqK215N8nUzTzyPiDjENSMePJiBfd11wPDhnBFf6dQra3l9e+RIHsRx/jxQpw7w1VcszcqZ0yd/BZEM2bqVB9BERzOww8OBZs2AkyfZtCeliAivD0mdzkQkbdYCv//OoF60iO0+P/qIM+IrBe2JE7zeN3Ik25Dmzctd3v37A5Uq+Wb8Ihmxbx/fVEZHs9oBAOrVA0aM4JvLIkUuvYYN8E3rkCFeH54CW0QuZS27kQ0ezE1lxYqxBWifPkCOHJf/s8uXM6QnTuSLWmQky7M6d07f9W0RXzp2DPjxR4b0/PmsVqhaFXjnHf7Oppw5uzaWDRzIZfCICIa1lzecAQpsEUnKWmDWLAb1338DxYtzdvHgg5cP6jNn+II3ciQDO1cu4P77OZuOTHX/jIhzzpwBpk7l7+xvv3HTY+nS7EXfpcuV91N07eqTgE5JgS0iDOrffmNQL1nCeufPP+eBGtmzp/3n/vuPG8i+/prX9ipWZMB37ZqxjmYi3hYXx9/x6GiGdWwsV44ef5whXb06O+n5MQW2SCizlq0/Bw9mK9ESJRjAPXumXVp19iyPxBw5EvjrLwZ6x47cKV67tt+/6EkISUjgJsmJE7nsffw4cO21QPfuDOl69dj8JEAosEVCkbU8jOONN7iEXbIkrzN37552UG/YwDAfP57X/cqU4U7x7t35IijiD6xlp73oaG4g27ePeyfateNlmmbNgKxZnR7lVVFgi4QSa4EpUxjUK1eyk9gXXwAPPJD6i1hcHFuDjhzJDTlZswL33MPZdMOGmk2L/3DVSn/7LUuysmcHWrXiTPquu65cfhgAFNgioSAxEfj5Zwb1v/8CN9/MdqBdu6Ye1Fu3slXol18CBw/y7OmhQ3lNu2hR349fJDWp1Uo3bcqDYtq3D7p9FApskWCWmMjWn2++CaxezZ2wEyZwaTBLiv/94+OBX3/lbHrmTL743X03Z9PNmwfUtT4JYqnVStetC/zvf8B997FWOkgpsEWCUWIiN4a9+SZnHmXLcid3586XBvWuXcDYsfzYu5elXIMHA717cxetiNNSq5WuUoUHzXTuzM2SIUCBLRJMEhKA779nUMfEsJ40Kgro1Ikz5qT3mzmTs+lp03ht+847+f2dd14a6iK+llqt9C23sGFJly5A+fJOj9Dn9H+lSDBISAAmTWJQr18PVKjAa3sdOiQP6v37uclszBgeC1i0KPDiizzKsmRJx4YvAoCbHGfOZEhPmeKulX7sMYb0bbeF9EZHBbZIIIuPZzC/9RbLripW5PW9e+91X3NOTOTJWiNHcuNZfDw35rz/PtC2bcCWuEiQcNVKR0dz2fvYMaBgQVYudOkC1K+v/RMXKbBFAlF8PJtBvPUWsGkTULkyr1m3b+9+cTt8mDXTo0YBmzezVvrJJ3lwQenSjg5fQlxqtdK5c/P3t0sXbnLUG8lLKLBFAkl8PPDNNzxsYPNmHlIweTJnymFhfCFctIiz6R9+4BJj/frcRHbPPVc+uEPEm1LWSmfL5q6Vbt06KGqlvUmBLRIILlzgLu8hQ/hCV60al7fbtOE1vePHeb70qFHcbJY/P8ux+vUDbr3V6dFLKNu2jSHtqpUOC+MlmUGDOKO+5hqnRxgwFNgi/iwujnXTb78NbN/OTTdTp3I2AnBZcdQozljOngVq1ADGjeOucM1WxCmp1UrXqcMjWu+7T813rpICW8QfxcWxy9jQodzNffvtbAzRqhVw+jS7kI0cCaxaxT7J3bvzKMtq1ZweuYSqY8d4eSY6mpscExO5t2LYML6BVBVCpimwRfzJ+fOcIQ8dyoYmNWvymMuWLdlSdMAAXsM+fZqNI0aOZNeyvHmdHrmEojNneIhMdDQwYwYv3dx8M/Dyy7wuXaGC0yMMKgpsEX9w7hzro4cNA3bv5jGVY8bw+L/vv+f3S5YAOXOys1P//lz+DuGaVHFI0lrpqVMZ2jfcADz6KEM6MlK/l16iwBZx0rlzDOZhw9gWtF49LoVffz2XvarzvTgAACAASURBVDt35oay8uWBjz9mbWqBAk6PWkJNWrXSXbu6a6WTNugRr1Bgizjh7FkG8jvvcINOgwacYR85wm5lCxey5KVDB+72rldPsxbxrbRqpdu25WWY5s3TPjtdvEKBLeJLsbHc1f3uu2wT2rAh8N57vD79wANsdnLzzbytZ0+gUCGnRyyhZu1adxmWq1b6zjs5k777blUfOEiBLeJtu3YBs2cDs2bx49gxoHFj4OGH2eSkWzcuJ7Zrx9l0kyZqxSi+tW2b+1zp//7j71+TJjxo4557VCvtJxTYIp525gyv97kCet063n7DDQzq3LkZ4PPmARERbC/64IO8bi3iK/v3u2ulFy/mbbVrA598wlrp665zdnxyCQW2SGYlJnJJe+ZMBvSff3InbY4cLMuqVo3XrFetYp1qWBhw113c6d2ypTbriPedOQOsXg2sWOH+WL3aXSs9dCg3OKpW2q8psEWuxt697mXu2bOBQ4d4e4UK3IyTmMhjLhcs4O0FCvB69RNPsB1jRIRzY5fgdvw43xwmDecNG/g7CfAQmNtuY2vQjh3VujaAKLBF0uPsWe7cdi1zr1nD2wsXBsqW5Yvejh3s4x0Tw2t+DRsCjz/OZfBKlXRdWjzv0CEG8sqV7nDessX982LFgOrVucRdvTo/ihdXxUGAUmCLpMZabr5xBfTChexClj07j6asWZPXAHfs4Itm/vwszXrsMaBRIy4zaqlbPMVaruoknTWvWMEmOy6lSjGQH3yQn6tVU8/uIKPAFnE5cCD5Mvf+/bz9xhs5iz56lC+Qa9YA+fK5A7pxY7YJVUCLJ1jLXdtJg3nlSuDgQf7cGP4+NmjgnjVXraqGOiFAgS2h69w5bhCbNYsbxv79l7fnzcsdssawWcSuXbwu2KABr0E3asTZiwJaMishAdi48dJl7RMn+PMsWXi5pVUrdzhXqcIDXyTkKLAldFjL68uuZe4FC3htOjycAV2kCGcxp07xvvXrA0895Q7oLPrfRTLhwgX+/iWdOa9axWY6AC+3VK7M3dqucK5YkdUGIlBgS7A7dAiYM8cd0nv38vYCBdix6exZznKOH2dAN2rEj9tuU0DL1Tt7lnsgkobzf/+x3A9gLX61akCfPu5wLlcOyJrV2XGLX9MrkgSXuDjgr7/cy9wrVvD2HDk4g3E5f579uRs3dge0Xizlapw6xZly0iXtmBi+EQT45rB6dV5OqVaNX5curaoByTAFtgQ2a1lj6ppBz5/PJhFhYTyK0sUYHkfZqBFDOjJSAS0Zd/Ro8mBesQLYtIm/hwB3ZVevDrRp4545lyihMirxCAW2BJ6jR4G5czmD/u03YM8e3p49O2fOAA8sqF3bvcR9++06WUgyZv/+S3dqb9/u/nlEBAO5Wzd3OKu9rHiRAlv834UL7HU8axYwYwZfPK3lZjHXsmO2bEDduu4l7ttvT74ELpIWa4GdOy+dOe/b576Pq/b+4Ye5rF2tmk5SE59TYIv/sRbYvJkBPW0al7nPnk1+n6xZgTp1eKJQ48Zc7lZAy5UkJrITWMoGJEeP8udhYUD58kCzZslrnPPlc3bcIlBgi784fhz4/Xfg11+B6dPZxCSpLFk4w2nenDPomjVV7iKXFx/Pfu5Jl7RXruQmMYBv+ipV4vGRrnCuVEnnPYvfUmCLM+LjgX/+AX75BZgyhS+sro07AJe7q1cH7ryTM+iaNZNvIhNJ6vx5YO3a5LPmf/9lcxyAvztVqwLdu7t3at96q/Y1SEBRYIvvbNvGgJ40CVi+3L1BDOBSZKVKQOvWQNOm3DCmgJaU4uOBw4cvbd25di33OgBcvq5WjdebXTPnsmXVmU4CngJbvOfkSW4Si4oC/vgDOHbM/TNXP+TWrTmLrl1bS5GhyFouUR88yI8DB9xfp/Zx5EjylZhChRjILVu6w7lUKdU4S1BSYIvnJCQwmL/8kmVXSU8SMoYvpC1aAPfeyw1juXM7N1bxnrg4dphLGrSXC+KkKy1JXXMN28UWKcIuYA0asM65SBEeEVmtmo6KlJCiwJbM2bgRGDWKM+lNm7hk6XLDDbz+3KULN4opoAOTtVwdSS1sUwvi48dTf5xs2dyBW6QI+2S7vk56e5EiPGdc15dFklFgS8YcOgSMGQP8/DOPmUxablW4MJe2u3bl6UI6Uch/nT17+aXnpGF86FDyN2IuxgDXXusO2apVk4duyjDOm1ezYZFMUGCHmsRE1pzu3cvGEAcO8AX58GFeHzx2jEf7nTwJnD7NNp9nz3K37fnz7l23AJA/PwO6Y0fOolWr6pyEBP67XukasOvDVdqUUs6cDNiiRdnJKzIy9RAuUoTXj3VAiojP6P+2QBEfz1aJ+/bxwzXzOXyYL9THj7uD9swZfpw7x48LF/iRmJh8w86VGMOdtVmzcnkyXz7u5G7fnqcMFS7svb9vqLOW/4bp3Yx1+DD/fVMKC+O/kytka9ZMO4CLFNFlCxE/5pHANsa0BPAxgHAAY621w1L8PDuArwDcBuAIgE7W2u2eeO50cR2j6JIzp/sMWm+LjWWv6337GLiuF9cjR9xBe/IkZzxnzvD+rtnshQsM6tReiC8nLIwzH1fQ5snD/wa5c3NZMl8+bugpUIBLmq4X9KJF2Qv5+us1W84sa/nvFxd36eeku6IvF8Ypu7u55MvnDthbbuEGvtSuAxcpAhQsqB3TIt4QFQUMHMi2thERwJAhvBzoRZkObGNMOIARAJoD2A1gqTFmqrU2JsndegM4Zq29xRjTGcA7ADpl9rnTJWVYA/w+V660QzsxkUGadNnYFbRHj/LjcsvG8fH8yMhsFuBs1hW0OXK4z2zOk4dBmz8/g7ZgweRBe9113OBVtGjwdf9KSEg7+K70+Wr+jKceO7VrvmnJmjV5yJYrl/Z14MKFg+/fWCTQREUB/fq5M2THDn4PeDW0jc1oqKR8AGNqA3jdWnvHxe9fAgBr7dAk95l58T5/G2OyANgPoLC9zJNHRkbaZcuWZWpsF5/8yj/L5H+DSx7PmOQfYWHJP4eHJ//a9TN/Zy3HmvRz0p+l/NraSz+S3u5aond9Tu02b0v5b5Tav1d6vk5625UeI+llhmzZ3L8DIhIYFi9OvRyxRInkJ7pdBWPMcmttZGo/88SSeDEAu5J8vxtAzbTuY62NN8acAHAtgMMpBtoPQD8AiIiI8MDQrsDTgZA0kCT9Ur7RAdybmVILwbRCMeln10fSN0WuN0phYcnfKF0uXFO7TURCW1q9A3bu9OrT+tWmM2vtaACjAc6wvf6Ebdu6N2mdPs1l7bNn+Y8RF8dlTddmrYwyhrOo8HCeIpUtG5cyc+XiNfS8ebnUnT8/PwoU4EehQvwoWNB/61BdM2zXLNjflq1dR256S5Ys/LdxzZIz+jlPnrTrj6+9VjuvRfxdyZJcBk/JyxNNT7wy7AFwY5Lvi1+8LbX77L64JJ4f3HzmfTlzpr55J2dO1hJnxMmT7l3aSWtUXeVQaW0gi4vj15ndQJY9uzv0U24gc13XLlTIfV37+uuBYsVCr+VnYqJz165T+xwbm/z7kyf5e5PaG4uUtc1pbSZzfai2WcT3hgxJfg0b4OvskCFefVpPBPZSAKWNMaXAYO4M4P4U95kKoAeAvwF0APD75a5fe1RsrOd2iefLx4+yZTM3pnPnGPh797p3jruCP2mJ1qlTnPnHxrpn/mfO8M9mdBZpDIM/SxZ38OfMyeDPk4d/r/z5GfwFC7qD37Vz/IYb+MYgEK61h4Xx7+jP52O7NjZeqWRr1arLdw/LkePyZVpJQ79QIf9dtREJJK6NZT7eJZ7pTWcAYIxpBeAjsKxrnLV2iDHmDQDLrLVTjTE5AHwNoBqAowA6W2u3Xu4xPbbpLJglJvLF3BX8SZugHD16aRMUV/C7Zv3x8Qz+jPwO5MgBlC/PQzv69gVuvPHKf0Yy7/z5S/tzX647WVxc6o9ToMDlu5El/bjmGs3eRXzscpvOPBLY3qDA9qHERIb6nj0M/v37GQ6HDrmD//hxfmzcmPzUrTx52JKyQwe+uyxUyLm/h5C1/PdMT7C7TsBKTdasyZuuXG5pvkgRlZuJeIACWzzr2DHgiy+AyZOB1au5TO9SoAC7aXXqBLRpw+V18W+uM6bTc7DHgQPpa+hypVm8GrqIpEqBLd61ZQswdizw66/A+vXJm4YUKQLUr89e402aMNAlsGWkZeqhQ+lrmXqlWbxapkqIUGCL7yQksKnA+PHA7NnckJH0d6x4caBpU+Cee3i+8TXXODZU8YGEBK7IpPdQkpMnU3+cXLmSh7rrPOzq1XlMpz9vMBTJAAW2OOfUKWDWLLbyW7gw+fVSY4BSpYCWLXkcZ7163Kkuoevs2StvrjtwANi2jRsqAVY+VKzI8HZ9VK6sWbkEJAW2+I9t24Dp04HvvgOWLEneMcgYoEwZ4K67OAuvV0+HkEjqrOXv0ooVyT8OHeLPw8JYfpk0xKtW1YqO+D0Ftvin+Hhg2TJg2jTgp5+AmJjky+dhYZw53XEH0LgxAzxvXufGK/7NWpY4pgzx3bvd97n5Zoa3azm9enUdEyt+RYEtgeHECWDePAb4tGnsKJdUWBhfaJs3Bxo1AurWZVmZyOUcPAisXMkPV4hv2eL+efHiyWfi1aqxQ6Bq0MUBCmwJTFu28Pr39OnA3LnuciLXSWHh4cDtt3P27QpwXbeU9Dh+nF3kXAG+ciUrHFw72gsXTh7i1atzv4VCXLxMgS2B78IF4J9/GOAzZnAp3RXarkNIsmQBatRgeDduDNSpE3p91OXqnTnDvgJJl9PXrHGXKebPn3wpvXp17rkID3d23BJUFNgSfI4eBX7/3R3gruuU2bOzLae17NRVo4Z7Bl6nDvuni6TX+fMM7aTL6f/+y/a+AN8QVq2afDm9QgX1bJerpsCW4GYtsGkTw3vWLAb5mTNcvsydmz3UExP5IlqzpnsGXquWAlwyLj6ey+dJZ+KrVrGEEeDvWaVKyWfilSrpd03SRYEtoSUujs1bZs5kgLt+j7Jn54zo+HGGfLZsDG3XDLxWLfXDlquTmMg9Fyl3qB89yp+Hh3PmnXRJvWpVVT3IJRTYEtoOH+amNdcM3LV8XqAAr3sfOcIX3OzZgdq13TPwmjXVQUuunrXs9Ofa1OYKcVf1gzFA6dLJl9OrVeN56BKyFNgiLtZyOdMV3vPnc8k8LIznflvLF1RrOduuXds9A69RQwEumbdvX/IAX7EC2LHD/fMSJS7doX7ddc6NV3xKgS2SlvPngT//dAf4ypW8PW9eBvi5c8CuXQzwnDm5ca1RI3eAa3OReMKRI8nLzFas4FG2Ltdff+kO9YgIlZkFIQW2SHodPAjMmeMOcNfyZfHiPOv7xAm2xAQY4HXrumfgkZEKcPGckye5Iz3pknpMDA9UAXhEadLl9OrVgVtu0bGlAU6BLXI1rAXWrmVwz5zJw0vOnWO5WNmy7HN+6BB3qAPc0FavnnsGHhnJ+4p4ytmzwH//JZ+J//cfN1oC7PyXciZerhz3akhAUGCLeMLZs8Aff7hn36tX8/Zrr+UO4OzZuaFt/Xrenju3O8AbNwZuu00vnOJ5cXHAunWXlpnFxvLnOXLw9LKkIa4jSf2WAlvEG/btS758fvAgby9XjkuTxrDUJyaGt+fJwwDv0AHo3FltVMV7EhJ4DTxp69UVK5IfSXrbbUDHjkCnTuydLn5BgS3ibYmJXJp01X4vWsSZT/bsrO++8Ua2V12xgkvo+fIB3bsD/ftztiPibUmPJF2+HJg9m5+NARo0ALp04ZtJlZU5SoEt4muxsbzm7Zp9r13L24sW5XGhsbHA1KkM9bp1gYce4oulGreIL23cCHz7LRAdzUs5WbIALVowvNu2VWMXByiwRZy2Zw9nND//zKDOnRvo3Zs7fb/5hrPuggWBnj056y5TxukRSyixljvSo6MZ4Dt3sgqidWuG95136s2kjyiwRfzJ2rXAm28C333HneWPPMKuat9+C/z0E3tVN2nC4G7XTqVi4luJicDffwMTJwLff89KiHz5gHvuYXg3aaLNk16kwBbxRzExwFtvMahz5mRwd+/OGfjo0ex+VaQIZ+J9+/I8ZhFfio9nW9/oaL6ZPHmSv5MdOzK8a9dW8xYPu1xgq8JexCkVKnAWExMDtG8PfPABu6cdOcLua9Onc8PaO+8AN9/MZckpU9znM4t4W5Ys3HMxfjxw4ADw44/coDZ2LPdelCoFvPgil9P9dPIXTDTDFvEXGzdyxh0VxWXwhx4Cnn+eAf3FF8CYMcDevSzB6dOHH8WLOz1qCUUnT/LNY3Q0N1UmJADly3PW3aULyxrlqmhJXCSQbNoEDBnCzWhZswL9+gEvvMClyGnTgJEjWT5mDHD33bzW3aIFj3AU8bXDh4EffmB4L1zI2yIjGdyq8c4wBbZIINqyBXj7bWDCBC5N9u3L4C5eHNi6lTPucePYsKVkSQb7gw+ydEzECbt2AZMmMbxXrFCN91VQYIsEsm3bGNzjx/Nghz59eN3wxhtZx/3zz5x1z5vHYG/fnsvpjRtrQ5A4Z+NGBnd0NLBhg/t6uKvGO08ep0folxTYIsFg+3Zg6FDgyy/5fe/ewEsv8ZhFgC+Ko0cz2I8eBUqX5nJ5z56a2YhzrGVvc1eN965drIq4+253jbf6mv8/BbZIMNmxAxg2jBvRAKBXLwZ3yZL8/tw5XlMcOZK7zbNnB+67j+Fdt65m3eKcxETgr78Y3q4a7/z53TXejRuHfI23AlskGO3axeAeO5YvhD17Mrhvusl9n//+A0aNAr7+mjt7b72Vy+XdugHXXOPY0EWS1XhPngycOqUabyiwRYLb7t2s1R4zhi+C3bsDAweydtvlzBkuR44cCSxbxiXJLl0Y3pGRIfnCKH7k7Fn2HYiOBn79FTh/HihRgqfadenC40FD5HdUgS0SCvbuZXCPHs2Twbp1AwYNurQmdvlyzrqjongISbVqDO7779dGIHHeyZPcSBkdzf77CQlsMtSlCwM8yGu8FdgioWTfPuDddzmbjosDunZlcKc8UOTECYb2yJFcOs+bl/d96CGgShVnxi6S1KFD7hrvRYt42+23u2u8b7jB2fF5gQJbJBTt3w+89x7w+edcYuzShcFdrlzy+1kLLF7M4J40ifetVYvB3bEjl89FnJZajXfDhvy9vvfeoKmEUGCLhLKDB4H33wdGjOC1ws6dgVdeYSvJlI4eBb76iuG9YQM3pvXowR3mqd1fxAkbNrhrvDduDKoabwW2iHB58YMPgP/9j9euO3ZkcN9666X3tRZYsIDXun/8kdfEGzZkcN9zj+pmxT9YC6xc6a7x3r074Gu8Fdgi4nb4MDB8OPDpp9w93qEDg7tSpdTvf/Agm7WMHs2WqIUKsQVqv37Jd6KLOCkxkX0HXDXehw+zxvvee9013gHQb1+BLSKXOnIE+PBD4JNPWAN7zz3Aq6+mveEsMRGYM4fL5VOncvdu8+a81n333TyoRMQfXLiQ/BzvU6fYY99V412rlt+WiSmwRSRtR48CH30EfPwxS2ratWNwV6uW9p/Zu5ed1kaP5jLk9dezVWrfvu5WqSL+ILUa75Il3TXelSr5VXgrsEXkyo4dY2h/9BFLvtq0YXDfdlvafyY+Hpgxg9e6p0/nC1+rVrzWfeedAbEEKSHkxAl3jfecOclrvLt08YtLPApsEUm/48e5TP7hh/y6dWvgtdfYEe1yduxgt7UvvmBJWUQEZ9y9e3MGLuJPDh3ite7oaOCPP3ibH9R4K7BFJONOnODGtOHDOftu1YrBXaPG5f/chQu8xj1yJGcx4eEstXnoIaBpUx4RKuJPdu5013ivXOmu8b7/fm5aK1jQZ0O5XGDr/xwRSV3+/Gy0sn07MGQIm6vUrMml7sWL0/5zWbPyRW72bGDTJuDpp1ki1qIFu629+y5nNyL+IiICeO45NmRZv56XgvbuZSXEdddxU+XEicDp07x/VBSvg4eF8XNUlE+GqRm2iKTPqVNsvvL++9xh3qIFZ9x16lz5z54/z3ruUaOAhQuBbNkY6v37Aw0a+NWmHxEAadd4V6nCYI+Lc983Vy5uwOzaNdNP67UlcWNMQQCTAJQEsB1AR2vtsRT3qQrgcwD5ACQAGGKtnXSlx1Zgi/ip06fZ7vS99zhTbtqUwV2/fvr+fEwMg/urr3iNvFw5Lpd37w4UKODdsYtcjcREXueOjmYwJyZeep8SJbgalUneDOx3ARy11g4zxrwIoIC19oUU9ykDwFprNxljbgCwHEB5a+3xyz22AlvEz505w+vU777L5iqNGzO4GzZM35+PjQW++46PsWQJkCMHN/s89BCX3jXrFn+U1u+lMakHeYYf3nvXsNsCmHDx6wkA2qW8g7V2o7V208Wv9wI4CKBwJp9XRJyWOzfwzDPAtm3cmLZuHdCoET/mz7/yn8+VC+jZk9fDV67k1z/+CNSuzRrwzz9nXbiIPylRIvXbfdB/ILOBXdRau+/i1/sBFL3cnY0xNQBkA7Alk88rIv4iVy7gqafYtvSjj3gYQ+PGnGnPnctrgVdStSoDeu9ezriNAQYMYGlN//68ZijiD4YM4e98Urly8XYvu2JgG2PmGGPWpPLRNun9LNfW0/w/0xhzPYCvAfSy1qa6bmCM6WeMWWaMWXZIu0hFAkvOnMATTwBbtrCOe/NmoFkzXtuePTt9wZ03rzuglyxhK8mvv2bzlho1gHHjuBQv4pSuXXkdu0QJvrEsUcJjG86uJLPXsDcAaGSt3XcxkOdba8umcr98AOYDeNta+0N6HlvXsEUC3LlzbKIybBh32NauzWvcLVpk7Pr08eMM7ZEjuWGtQAHg+eeBxx7jsrxIEPHmNeypAHpc/LoHgCmpPHk2AD8B+Cq9YS0iQSBHDuCRRzjT/uwzhnbLlgzuGTPSN+MGeCb3Y48Ba9awJKx2beCll4CbbuIS/Llz3v17iPiJzAb2MADNjTGbADS7+D2MMZHGmLEX79MRQAMAPY0xqy5+VM3k84pIoMieHXj4YTZRGTkS2LePXdNq1gSmTUt/cBvD5fVp03iMYsWKvHZ+yy183KR1sSJBSI1TRMS34uJYgz1kCOtWIyPZWap164yXcs2bx25sf/3FjlOvvQZ06wZkyeKNkYt4nVqTioj/yJYN6NOHu8m/+ILHe7Zpw+CeMiX9M26Au9H/+IMnhRUsCPTqBdx6KztTeaAmVsSfKLBFxBlZswIPPsjezV9+ycNG2rVjDfbkyekPXGPY33zZMv65rFl54lLVqjxK0U9XEUUySoEtIs7KmpVNU9avByZMYAe0e+9lcP/wQ8aCu3174N9/eVDDuXP8vkYN4LffFNwS8BTYIuIfsmRhP/GYGJZxnT8P3HcfD1v47rv0B3d4OGfYMTGs2z50iDPw+vXT14FNxE8psEXEv2TJwo1ja9fy2ML4ePYYr1SJ16YTEtL/OL168Vr5Z5+xhWrjxmzmcrnjQUX8lAJbRPxTeDhw//2sv46O5m1duvA4zoycipQtG8vKNm9mz/PVq1nL3bo1e5iLBAgFtoj4t/BwoHNn4L//gPHjGeBVq3KZPCNy5nT3PH/7bdZyV68OdOjA2byIn1Ngi0hgCAsDevQAVq0CypfnMnnv3hnvLZ4nDzulbdvG+u+ZM7nc3q0bZ+EifkqBLSKBpVQptigdOJDlYNWrX91pXtdcAwwezOB+7jmWhJUrxxrxHTs8P26RTFJgi0jgyZoVeOst4PffOcOuVYvXp6+mWUqhQsA773Cp/JFHuEO9dGng0Ud53KeIn1Bgi0jgatSIddd33QU88ww/HzhwdY913XXAxx9zWbxXL2DUKODmmzn71nG/4gcU2CIS2K69lsvZn3/OOuvKlXld+mrdeCPDev16nsc9fDhPBnvlFR71KeIQBbaIBD5jgIceYnvSokV5jOczz7D5ytW6+WZ2XluzhqeLvfUWr58PGQKcOuW5sYukkwJbRILHrbcCS5bw+vPw4ay33rAhc49ZvjwwaRJ3pzdowNPBbroJ+OADtlEV8REFtogEl5w5gU8/5clfO3dyF/m4cZnvJV6lCh9zyRI+5rPP8izuESMyN5MXSScFtogEpzZtuCGtVi3Wa3fu7Jlr0DVq8Br5ggUM7EcfBcqU4VGhFy5k/vFF0qDAFpHgVawYMGsWMHQoN6ZVrcoOZ57QoAFDe9Ys7jDv0weoUIH9z9Pb71wkAxTYIhLcwsOBF19kUIeHM2jfeMMzoWoM0Lw5DxOZOhXInZsd0ypXBn788erqwkXSoMAWkdBQowYP+7j/fuC113hy186dnnlsY4C772bHNddRoB06AJGRwLRpOotbPEKBLSKhI18+djL76iuGd5UqnAl7SlgYz/Bes4YlYceP81SwOnWAuXMV3JIpCmwRCT0PPMDALl2aM+F+/TxbohUeDnTvzpKyUaOA3bt5DneTJsAff3jueSSkKLBFJDTdcgvD84UXgLFjuXz977+efY6sWflmYNMmtj1dtw6oXx+48042eRHJAAW2iISubNmAYcOA2bO5fF2jBvDJJ55fus6RA3j8cWDLFh408s8/wO23A+3b85xvkXRQYIuING3K2XWLFsATT3ADmTcO/MidG3j+eR7pOXgwTxurUgXo0iXzHdkk6CmwRUQAoHBhlmZ9+ikwZw5Ls2bP9s5z5csHvPoqg/ull4BffmENd69evE0kFQpsEREXY9i57J9/gIIFOeN+/nkgLs47z1ewIA8T2bqVM/voaHZNe/hhblQTSUKBLSKSUuXKwNKlPAHsvfeAunV5Tra3FCnCw0q2bAH69mWb01tuAZ566urP95ago8AWEUlNrlw8Y3vyZAZptWqsrfZmLXWxYsBnn/F69v33cwPcTTdx2fzoUe89rwQEBbaIyOW0bw+sXg3cdhvQsyfQtStw4oR3n7NUKZ4wtm4d0LYtd5aXKsWNaidPeve5xW8pqu3oFwAAFIRJREFUsEVErqR4cXYqe/NNth6tVo39w72tTBlg4kTuYG/aFHj9dQb3O+8AZ854//nFryiwRUTSIzwcGDQIWLSIy+L16gFvv+2bk7kqVeLS/LJlQM2aPMzkppvYjOXcOe8/v/gFBbaISEbUrg2sWsWe4QMHsuXonj2+ee7bbgOmT2eHtgoVgCef5Oa0UaO8t5Nd/IYCW0Qko/Ln51L1l19yN3nlysCUKb57/rp1gXnzuEwfEcHd7OXK8VATncUdtBTYIiJXwxhuQluxAihZEmjXDhgwADh71ndjaNKE53xPmwZccw3QowdQsSIwaZLO4g5CCmwRkcwoUwb4+2/gmWdYBnb77Txe01eMAVq1ApYv51Gh4eFA587cGDd1qo70DCIKbBGRzMqWDXj/feC334DDh3ny14gRvg1LY4B77uGO8qgoHhfati03qc2cqeAOAgpsERFPueMO1mw3acIWp+3aMcB9KTycTVfWrWPHtAMHgJYtgYYNgYULfTsW8SgFtoiIJxUpAvz6K/Dhh5xxV6nCDWK+liUL8OCDwMaNnO1v3szQbtHCt0v24jEKbBERTwsLY8nV4sVA3rxsevLyy8CFC74fS/bs3Ay3ZQuX7ZctA6pWBR57TO1OA4wCW0TEW6pV42aw3r2BoUOB+vV5MpcTcubkxrhNm4B+/dizvEwZbpRTKVhAUGCLiHhT7tzAmDHA99/zUI+qVbkpzCnXXsuwXrmSJWADBgDVqwMLFjg3JkkXBbaIiC906MAd3FWqAN26Ad27A6dOOTeeypV5bf2774Djx4FGjYBOnYCdO50bk1yWAltExFciIhiSr7/OWXa1auyU5hRj2GJ13TqOaepUdkwbPJhlYeJXFNgiIr6UJQvw2mtcgr5wAahTh6dvOdmZLFcujmnDBuDuuxne5ctzGV/1235DgS0i4oR69XiISLt2PH2rRQtg715nxxQRwbam8+ez1WnHjqwpX73a2XEJAAW2iIhzChTgNeQxY9jetEoV1nA7rWFD7m7/7DOGdbVq3Jx25IjTIwtpCmwREScZA/Tpw4AsXpxL0o8/7vw511myAA8/zDKwAQOA0aOB0qXZhCU+3tmxhahMBbYxpqAxZrYxZtPFzwUuc998xpjdxpj/ZeY5RUSCUrlybLTy5JPAp5+yB3hMjNOjAgoW5HhWreJM+9FH+dmJ7m0hLrMz7BcBzLXWlgYw9+L3aXkTgBrZioikJXt2tjSdNg3Yt4+HiIwa5R8bvypWBObM4Ylgp0/z2naHDsD27U6PLGRkNrDbAphw8esJANqldidjzG0AigKYlcnnExEJfq1a8dpxvXrAQw8xGP2hjajrRLCYGODNN4EZM7ib/NVXVQbmA5kN7KLW2n0Xv94PhnIyxpgwAB8AeDaTzyUiEjquu46Hh7z3HvDLL9yQ5i/dyHLmBAYNAtav5y73N98EypYFvv3WP1YDgtQVA9sYM8cYsyaVj7ZJ72ettQBS+5caAGC6tXZ3Op6rnzFmmTFm2aFDh9L9lxARCUphYcCzz3IHec6cXIZ+9VX/2fR1441AdDSP7SxUCOjShTvMV61yemRBydhMvBsyxmwA0Mhau88Ycz2A+dbasinuEwWgPoBEAHkAZAPwmbX2cte7ERkZaZctW3bVYxMRCSqnT/OErfHj2WwlKgooWdLpUbklJPD87YEDuXzfty/w1lsMckk3Y8xya21kaj/L7JL4VAA9Ln7dA8CUlHew1na11kZYa0uCy+JfXSmsRUQkhTx5gC+/5Ix2zRoeIjJpktOjcgsP5ylgGzfyjcXYsSwD++QTZ44VDUKZDexhAJobYzYBaHbxexhjIo0xYzM7OBERSaFzZy45V6jArx98kLNvf1GgAPDRR9w0FxkJPPEE31zMmeP0yAJeppbEvUlL4iIilxEfz0M6hgwBbrmFG76qV3d6VMlZC0yZAjz9NLBtG9C+PfDBB0CpUk6PzG95c0lcRESckCULd2fPmwecPQvUqsUwdPIQkZSM4S7ymBi+sZg5k2VggwYBZ844PbqAo8AWEQlkDRvynO3Wrbmj/M47gf37nR5VcjlyAC+/zOvbHTowvMuWBSZOVBlYBiiwRUQCXcGC7EA2ciRLrKpUYVMTf1OsGPDNN8Cff7LOvGtXoH59YMUKp0cWEBTYIiLBwBigf39g2TKgaFF2S3vqKeD8eadHdqk6dYAlS3hK2caN3JzWty9w8KDTI/NrCmwRkWBy663AP//wkI6PPuK17fXrnR7VpcLDeUrZxo088GT8eKBMGY5ZZWCpUmCLiASbHDl4wtbUqcCuXcBtt7GpiT9eL77mGmD4cJaB1arFVYEqVYBZOnoiJQW2iEiwuvtuBmHt2pzN9u3LjmT+qHx5XnefOhWIiwPuuANo2xbYssXpkfkNBbaISDC74QbOVgcN4iy7a1f/XXI2hm8y1q4Fhg0D5s5lg5iXXvKv5jAOUWCLiAS7sDDWbL/3HtuZdugAnDvn9KjSlj078MILvL7dqRPDu0wZ7jD3x2V9H1Fgi4iEimefBUaM4LJzmzb+f4b1DTcAX33F08qKFQMeeACoW5c74UOQAltEJJQMGACMG8fl5jvvBE6dcnpEV1arFsvAxo0Dtm4FatQAevcGDhxwemQ+pcAWEQk1vXqxy9hffwHNmgHHjjk9oisLC+O4N24EnnmGM+8yZdiONS7O6dH5hAJbRCQUderE7mirVgGNGwdO05J8+Xgtfs0aLo8/+yxQubJ/dnbzMAW2iEioatMG+OUXzlobNgT27nV6ROlXtiwwfTrw66888KRVK+4w37TJ6ZF5jQJbRCSUtWgB/PYbsHs30KABsGOH0yPKmLvu4mz73XeBBQvY6e2FFwLj2nwGKbBFREJdgwbchHbkCA/jCLRZarZswHPPcaWga1eGd5kywIQJ/nXcaCYpsEVEhDuvXWdrN2jA5iWB5rrrgC+/5I7yEiWAnj150Mg//zg9Mo9QYIuICFWtyuM5jeE17UA99rJGDe6AnzCBS/w1a3KHub+dE55BCmwREXErXx5YtAjIkwdo0oRNSwJRWBjQvTuXyZ9/HoiK4jL5e+8FbBmYAltERJK7+WbOtAsXBpo3B+bPd3pEVy9vXuCdd7jE37Ahw7tiRWDaNKdHlmEKbBERuVREBEO7RAl2RPvtN6dHlDmlS7OEbcYMzr5bt2Yp2IYNTo8s3RTYIiKSuuuvZ6lU+fKs2f7pJ6dHlHktW/LI0Q8+AP78k7PtZ58FTp50emRXpMAWEZG0FSoE/P47EBkJ3HcfW5oGumzZgKef5vXtHj2A4cM5Ax83zq/LwBTYIiJyeddcwzO169cHunUDxo51ekSeUbQo/y7//MPr9r1786CRxYudHlmqFNgiInJlefKwFegddwB9+wKffOL0iDwnMpLL419/DezZA9SuzR3mftaqVYEtIiLpkzMn8PPPQPv2wBNPAMOGOT0izzGGqwcbNgAvvQRMmsQysGHDgPPnWRZWsiQ3rJUsye99PURrrc+fND0iIyPtshA9pFxExK/Fx/Pa78SJwKBBwBtvMPCCyZYtPMZzyhSgSBHg+PHk9du5cgGjR7MVqgcZY5ZbayNT+5lm2CIikjFZsvA86j59gLfeYrD56eTvqt18M1cTZs7keeEpm63ExgIDB/p0SFl8+mwiIhIcwsOBUaM40/zwQ/YgHzGCS8bBpEUL4MKF1H+2c6dPh6LAFhGRqxMWBnz0EZA7NzB0KHDmDEujsgRZtJQokfqxoxERPh1GkL0VEhERnzIGePttLo1//TXQpUvA9upO05AhXElIKlcu3u5DQfY2SEREHDFwIEPs6ae5PP7DD0COHE6PyjNcG8sGDuQyeEQEw9rDG86uRIEtIiKe8dRTDO2HHwbuvpubtnLndnpUntG1q88DOiUtiYuIiOf0789zqH//nU1WTpxwekRBQ4EtIiKe9cADwLffAkuWAM2aAUePOj2ioKDAFhERz7vvPp7u9d9/QKNGwIEDTo8o4CmwRUTEO1q3Bn79lV3DGjYEdu92ekQBTYEtIiLe06wZu4Xt3Qs0aABs2+b0iAKWAltERLyrXj1g7lz2465fnwdsSIYpsEVExPtuvx2YP59tPhs04LVtyRAFtoiI+EblysDChUDWrNyIphMZM0SBLSIivlO2LLBoEZAvH9C0KfDnn06PKGAosEVExLdKlWJoX3cdT8OaO9fpEQUEBbaIiPhe8eJcHr/pJuCuu4Bp05wekd9TYIuIiDOKFuVGtEqVgHbteGCIpEmBLSIizrn2WmDOHKBmTaBTJx7RKalSYIuIiLPy52dzlcaNgR49gFGjnB6RX8pUYBtjChpjZhtjNl38XCCN+0UYY2YZY9YZY2KM+b/27jVErvKO4/j3n4u5iUioWkncrC+0NEi9BfGCqGmEaBsFFW3dFhsqQbBosY1V9IWi0aqxUfFGNBLrrQkYmyBiTdQYX5RqbLWtSUtVjFrSpraENlm1qP++OFO6bVa2Otl55pz5fmBhzpmZPT8ewvxyznnm2ehv57iSpIaZMqVaxvTUU+GCC2DJktKJuk67Z9iXAU9n5kHA063t4fwYuCkzvwgcBWxr87iSpKaZOBFWrYKzzoJLLoFFi0on6irj2nz/6cCJrcf3A+uBHwx9QUTMBMZl5lqAzNzR5jElSU21xx7wyCMwaRJceSXs3FkVd0TpZMW1W9j7ZebW1uM/AfsN85qDge0RsQo4EFgHXJaZH7V5bElSE40bB8uXw+TJcP31VWnfckvPl/aIhR0R64DPD/PUFUM3MjMjIj/hGMcDhwNvASuAbwHLhjnWAmABQF9f30jRJElNNWYM3HVXVdpLlsDgINx9N4wdWzpZMSMWdmbO+aTnIuLPEbF/Zm6NiP0Z/t70O8DLmflG6z0/BY5mmMLOzKXAUoBZs2YNV/6SpF4RATffXE1Iu/baqrTvv786A+9B7U46WwOc13p8HrB6mNe8COwdEfu0tmcDm9o8riSpF0TANdfAddfBww/D2WfDBx+UTlVEu4X9Q+DkiPgDMKe1TUTMioh7AVr3qr8PPB0RvwECuKfN40qSesnll8Ott8Jjj1Wror33XulEHdfWdYXM/Cvw5WH2bwTOH7K9FvhSO8eSJPW4iy6q7mkvWFCtP75mDey5Z+lUHeNKZ5Kk+jj//Gr50g0bqr/0tX176UQdY2FLkuplYABWroSNG6u/qf3uu6UTdYSFLUmqnzPOgNWrYdMmOPFE2Lp1xLfUnYUtSaqnU06BJ56AN9+EE06At98unWhUWdiSpPo66SR46inYtg2OPx5ef710olFjYUuS6u3YY+GZZ2DHjqq0N28unWhUWNiSpPo74ghYvx4+/ri6PP7KK6UT7XYWtiSpGQ45pPq614QJ1US0F14onWi3srAlSc1x8MHw/PMwdSrMmVMVeENY2JKkZunvr4p62jSYO7ealNYAFrYkqXmmTYPnnqvOuOfNq5YxrTkLW5LUTPvuW80eP/RQOPNMWLGidKK2WNiSpOaaOhXWrYNjjoFzz4Xly0sn+swsbElSs+21Fzz5ZLXu+Pz5cOedpRN9Jha2JKn5Jk+u7mPPmwcXXgiLF5dO9KlZ2JKk3jBxIjz6KJxzDixcCFdfDZmlU/3fxpUOIElSx4wfDw89BJMmwVVXwc6dcMMNEFE62YgsbElSbxk7FpYtqy6T33QTDA7CbbfBmO6+6GxhS5J6z5gxcPvtVWkvXlyV9j33VGXepSxsSVJvioAbb4QpU6r72YOD8MAD1WXzLmRhS5J6V0R1L3vKFLj0Unj//WqBlQkTSifbRXdfsJckqRMWLqwuka9eDaedVp1tdxkLW5IkqL6ffd991cpoRx4JfX3Vve7+/mpmeWFeEpck6d/mz4eXXoI77vjPvi1bYMGC6vHAQJlceIYtSdJ/e/zxXfcNDsIVV3Q+yxAWtiRJQ7311qfb3yEWtiRJQ/X1fbr9HWJhS5I01KJF1YIqQ02eXO0vyMKWJGmogQFYuhRmzKi+pz1jRrVdcMIZOEtckqRdDQwUL+j/5Rm2JEk1YGFLklQDFrYkSTVgYUuSVAMWtiRJNWBhS5JUAxa2JEk1YGFLklQDFrYkSTVgYUuSVAMWtiRJNWBhS5JUAxa2JEk1YGFLklQDFrYkSTUQmVk6w7Ai4i/Alt38az8HvLubf6d25Th3huPcGY5zZzjOlRmZuc9wT3RtYY+GiNiYmbNK52g6x7kzHOfOcJw7w3EemZfEJUmqAQtbkqQa6LXCXlo6QI9wnDvDce4Mx7kzHOcR9NQ9bEmS6qrXzrAlSaqlnijsiJgbEb+PiNci4rLSeZoqIu6LiG0R8dvSWZosIg6IiGcjYlNEvBoRF5fO1EQRMTEiXoiIV1rjfHXpTE0WEWMj4lcR8XjpLN2q8YUdEWOBO4BTgJnA1yNiZtlUjbUcmFs6RA/4EPheZs4EjgYu9N/0qPgAmJ2ZhwKHAXMj4ujCmZrsYmBz6RDdrPGFDRwFvJaZb2TmP4GfAKcXztRImbkB+FvpHE2XmVsz85etx/+g+pCbVjZV82RlR2tzfOvHST+jICKmA18B7i2dpZv1QmFPA94esv0OfripISKiHzgc+EXZJM3Uukz7MrANWJuZjvPouAW4FPi4dJBu1guFLTVSROwJPAp8NzP/XjpPE2XmR5l5GDAdOCoiDimdqWki4qvAtsx8qXSWbtcLhf1H4IAh29Nb+6TaiojxVGX9UGauKp2n6TJzO/AsztEYDccBp0XEm1S3LGdHxINlI3WnXijsF4GDIuLAiNgD+BqwpnAm6TOLiACWAZsz80el8zRVROwTEXu3Hk8CTgZ+VzZV82Tm5Zk5PTP7qT6fn8nMbxSO1ZUaX9iZ+SHwHeBnVJNzVmbmq2VTNVNEPAL8HPhCRLwTEd8unamhjgO+SXUm8nLr59TSoRpof+DZiPg11X/812amXzlSMa50JklSDTT+DFuSpCawsCVJqgELW5KkGrCwJUmqAQtbkqQasLAlSaoBC1uSpBqwsCVJqoF/AeE4mHiQHLFYAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<Figure size 576x576 with 1 Axes>"
      ]
     },
     "metadata": {
      "needs_background": "light"
     },
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Load motion primitives (mp)\n",
    "mp_path = 'motion_primitives_search_tutorial/'\n",
    "mp_file = 'V_9.0_9.0_Vstep_0_SA_-0.2_0.2_SAstep_0.4_T_0.5_Model_BMW320i.xml'\n",
    "\n",
    "vehicle_type_id = 2\n",
    "automaton = generate_automata(vehicle_type_id, mp_file= mp_path+mp_file, search_tutorial=True)\n",
    "\n",
    "# plot motion primitives\n",
    "\n",
    "plt.figure(figsize=(8,8))\n",
    "\n",
    "for mp in automaton.Primitives:\n",
    "    plot_motion_primitive(mp)\n",
    "plt.show()\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Greedy-Best-First Search (GBFS)\n",
    "As mentioned in the tutorial on uninformed search, GBFS is based on the Best-First Search and uses as evaluation function f(n) the heuristic cost h(n). For this application, we need a heuristic which estimates the time to reach the goal. Therefore, we calculate the euclidean distance of the final matched state to the goal region and divide it by the velocity in the final matched state. This is a very simple heuristic, but it works for our example.\n",
    "\n",
    "Before we run the algorithm you can have a look at the implementation of the Best-First Search and the evaluation function.\n",
    "\n",
    "```python\n",
    "def search_alg(self):\n",
    "    '''\n",
    "    Implementation of Best-First Search (tree search) using a Priority queue\n",
    "    '''\n",
    "    # First node\n",
    "    initial_node = PrioNode(path=[[self.initial_state]], primitives=[], tree_depth=0, current_cost=0)\n",
    "   \n",
    "\n",
    "    # add current node (i.e., current path and primitives) to the frontier\n",
    "    f = self.evaluation_function(initial_node)\n",
    "    self.frontier.insert(item=initial_node, priority=f)\n",
    "\n",
    "    while not self.frontier.empty():\n",
    "        # Pop the shallowest node\n",
    "        current_node: PrioNode = self.frontier.pop()\n",
    "\n",
    "        # Goal test\n",
    "        if self.reached_goal(current_node.path[-1]):\n",
    "            solution_path = self.remove_states_behind_goal(current_node.path)\n",
    "     \n",
    "            # return solution\n",
    "            return solution_path, current_node.primitives\n",
    "\n",
    "        # Check all possible successor primitives(i.e., actions) for current node\n",
    "        for succ_primitive in current_node.get_successors():\n",
    "\n",
    "            # translate/rotate motion primitive to current position\n",
    "            current_primitive_list = copy.copy(current_node.primitives)\n",
    "            path_translated = self.translate_primitive_to_current_state(succ_primitive, \n",
    "                                                                        current_node.path[-1])\n",
    "            # check for collision, if is not collision free it is skipped\n",
    "            if not self.check_collision_free(path_translated):\n",
    "                continue\n",
    "\n",
    "            current_primitive_list.append(succ_primitive)\n",
    "\n",
    "            path_new = current_node.path + [[current_node.path[-1][-1]] + path_translated]\n",
    "            child_node = PrioNode(path=path_new, primitives=current_primitive_list,\n",
    "                                  tree_depth=current_node.tree_depth + 1, \n",
    "                                  current_cost=current_node.current_cost)\n",
    "            f = self.evaluation_function(current_node=child_node)\n",
    "            print(f)\n",
    "\n",
    "            # Inserting the child into the frontier:\n",
    "            self.frontier.insert(item=child_node, priority=f)\n",
    "\n",
    "    return None, None\n",
    "\n",
    "def evaluation_function(self, current_node: PrioNode) -> float:\n",
    "    \"\"\"\n",
    "    Evaluation function of GBFS is f(n) = h(n)\n",
    "    \"\"\"\n",
    "\n",
    "    current_node.current_cost = self.heuristic_function(current_node=current_node)\n",
    "    return current_node.current_cost\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Short reminder: When executing the following code block, you will see a \"visualize\" button directly beneath the \"iteration\" slider if you are running this notebook for the first time. Otherwise you can always find the button on the bottom.\n",
    "\n",
    "Click the \"visualize\" button and let the search algorithm run through, once it's completed, you can use the slider to see all the iterations step by step."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "2bd09dd5ca3248fba61cdb5824c918e4",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='iteration', max=1), Output()), _dom_classes=('widget-int…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "93fb5f112da34e8e91c6ca54724edc47",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(ToggleButton(value=False, description='Visualize'), Output()), _dom_classes=('widget-int…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "gbfs_planner = tree_search.GreedyBestFirstSearch(scenario=scenario, planningProblem=planning_problem, \n",
    "                                                automaton=automaton)\n",
    "scenario_data = scenario_data = (scenario, gbfs_planner.initial_state, gbfs_planner.egoShape, planning_problem)\n",
    "\n",
    "# run the planner\n",
    "display_steps(scenario_data=scenario_data, algorithm=gbfs_planner.search_alg, \n",
    "              config=gbfs_planner.config)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## A* Search\n",
    "\n",
    "A* uses the evaluation function f(n)= g(n) + h(n). So let's have a look at the new evaluation function and then let's run the A* Search.\n",
    "\n",
    "```python\n",
    "def evaluation_function(self, current_node: PrioNode) -> float:\n",
    "    \"\"\"\n",
    "    Evaluation function of A* is f(n) = g(n) + h(n)\n",
    "    \"\"\"\n",
    "\n",
    "    if self.reached_goal(current_node.path[-1]):\n",
    "        current_node.path = self.remove_states_behind_goal(current_node.path)\n",
    "    # calculate g(n)\n",
    "    current_node.current_cost += len(current_node.path[-1]) * self.scenario.dt\n",
    "\n",
    "    # f(n) = g(n) + h(n)\n",
    "    return current_node.current_cost + self.heuristic_function(current_node=current_node)\n",
    "\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "0abe9d46e25d4a0b8fdd55fc5adb15fd",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(IntSlider(value=0, description='iteration', max=1), Output()), _dom_classes=('widget-int…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/vnd.jupyter.widget-view+json": {
       "model_id": "3acb6be8ee10403ba86830a7cf803074",
       "version_major": 2,
       "version_minor": 0
      },
      "text/plain": [
       "interactive(children=(ToggleButton(value=False, description='Visualize'), Output()), _dom_classes=('widget-int…"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "astar_planner = tree_search.AStarSearch(scenario=scenario, planningProblem=planning_problem, \n",
    "                                                automaton=automaton)\n",
    "\n",
    "# run the planner\n",
    "display_steps(scenario_data=scenario_data, algorithm=astar_planner.search_alg, \n",
    "              config=astar_planner.config)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Congratulations! You finished the tutorial on informed search and commonroad search. Now you are ready to implement your own search algorithms and heuristics to solve more complex planning problems."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}